class Solution {
    /**
        常规思路:用一个map存所有元素，然后遍历判断哪个元素不在即可
        不过要想不适用额外空间，就要改造nums数组，让其成为map
        则假设如果x存在数组中，则让index为x的元素变为负数
        那么最终nums[x]如果大于0，那么元素x+1就不存在
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            // 如果x存在数组中，则让index为x的元素变为负数
            int index = Math.abs(nums[i])-1;
            nums[index] = -Math.abs((nums[index]));
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                ans.add(i+1);
            }
        }
        return ans;
    }
}